// input amount -> money count
// 1,2,5,10,20,30,50,100
pub fn dp_rec_mc(amount: u32) -> u32 {
    let mut ans = 0;
    let mut amount = amount;
    while amount > 0 {
        if amount >= 100 {
            ans += amount / 100;
            amount %= 100;
        } else if amount >= 50 {
            ans += amount / 50;
            amount %= 50;
        } else if amount >= 20 {
            ans += amount / 20;
            amount %= 20;
        } else if amount >= 10 {
            ans += amount / 10;
            amount %= 10;
        } else if amount >= 5 {
            ans += amount / 5;
            amount %= 5;
        } else if amount >= 2 {
            ans += amount / 2;
            amount %= 2;
        } else {
            ans += amount;
            amount = 0;
        }
    }
    ans
}
